/**
 * Created With IntelliJ IDEA
 * Description:
 * 牛客网：BM20 数组中的逆序对
 * 链接：https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=295&tqId=23260&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 * User: DELL
 * Data: 2022-10-31
 * Time: 21:35
 */
public class Solution {
    //记录逆序对的总数
    int count = 0;
    public int InversePairs(int [] array) {
        //当数组元素少于两个时，逆序对为0
        if (array.length < 2) {
            return 0;
        }
        //进入归并
        mergeSort(array,0, array.length - 1);
        return count;
    }
    public void mergeSort(int [] array, int left, int right) {
        int mid = left + (right - left) / 2;
        if (left < right) {
            //左边数组
            mergeSort(array,left,mid);
            //右边数组
            mergeSort(array,mid + 1,right);
            //归并左右数组
            merge(array,left,right,mid);
        }
        return;
    }

    public void merge(int [] array,int left,int right,int mid) {
        //创建临时数组，用于存放排序好后的数组
        int [] arr = new int[right - left + 1];
        //保留原数组的起点下标
        int tmp = left;
        //左边数组的起始下标
        int l = left;
        //右边数组的起始下标
        int r = mid + 1;
        //临时数组的下标起点
        int c = 0;
        while (l <= mid && r <= right) {
            if (array[l] < array[r]) {     //题目已经事先保证数组中没有重复的元素
                // 当左子数组的当前元素小的时候，跳过，无逆序对
                //放入临时数组
                arr[c] = array[l];
                //临时数组下标加一
                c++;
                //左子数组的下标加一
                l++;
            } else {
                // 当左子数组的当前元素大的时候，有逆序对，计算逆序对
                //放入临时数组
                arr[c] = array[r];
                //临时数组下标加一
                c++;
                //逆序对的个数 = mid - left + 1;
                count += mid - l + 1;
                count %= 1000000007; //题目要求,防止count越界
                //右子数组的下标加一
                r++;
            }
        }
        //将左子数组和右子数组中剩余的元素拷贝到临时数组
        while(l <= mid) {
            arr[c] = array[l];
            c++;
            l++;
        }
        while(r <= right) {
            arr[c] = array[r];
            c++;
            r++;
        }
        //将临时数组中排序好的元素拷贝到原数组中
        for (int num : arr) {
            array[tmp++] = num;
        }
        return;
    }

}





